package com.example.demo.algorithm.lesson.basic.class3;

import com.example.demo.algorithm.lesson.basic.class1.ArrayCompareHelper;

import java.util.Arrays;

/**
 * @author liweizhi
 * @date 2020/5/7
 */
public class QuickSort {
    // 按照最右面的元素的值,分区
    public static int partition(int[] arr, int left, int right) {
        if (left > right) {
            return -1;
        }
        if (left == right) {
            return left;
        }
        int lessEqual = left - 1;
        while (left < right) {
            if (arr[left] <= arr[right]) {
                swap(arr, ++lessEqual, left);
            }
            left++;
        }
        swap(arr, ++lessEqual, right);
        return lessEqual;
    }

    // 按照最右面的元素的值,分区
    public static int[] netherLandsPartition(int[] arr, int left, int right) {
        if (left > right) {
            return new int[]{-1, -1};
        }
        if (left == right) {
            return new int[]{left, right};
        }
        int lessRight = left - 1;
        int moreLeft = right + 1;
        int cursor = left;
        int num = arr[right];
        while (cursor < moreLeft && cursor <= right) {
            if (arr[cursor] < num) {
                swap(arr, ++lessRight, cursor);
                cursor++;
            } else if (arr[cursor] == num) {
                cursor++;
            } else if (arr[cursor] > num) {
                swap(arr, --moreLeft, cursor);
            }
        }
        return new int[]{lessRight, moreLeft};
    }

    public static void swap(int[] arr, int indexA, int indexB) {
        if (indexA == indexB) {
            return;
        }
        int temp = arr[indexA];
        arr[indexA] = arr[indexB];
        arr[indexB] = temp;
    }

    public static void quickSort1(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        process1(arr, 0, arr.length - 1);
    }

    public static void process1(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        int partition = partition(arr, left, right);
        process1(arr, left, partition - 1);
        process1(arr, partition + 1, right);
    }

    public static void quickSort2(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        process2(arr, 0, arr.length - 1);
    }

    public static void process2(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        int[] netherLandsPartition = netherLandsPartition(arr, left, right);
        process1(arr, left, netherLandsPartition[0]);
        process1(arr, netherLandsPartition[1], right);
    }

    public static void quickSort3(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        process2(arr, 0, arr.length - 1);
    }

    public static void process3(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        // 从区域中随机找一个数,然后和最右面的数交换
        int theIndex = (int) Math.random() * (right - left + 1) + left;
        swap(arr, theIndex, right);
        int[] netherLandsPartition = netherLandsPartition(arr, left, right);
        process1(arr, left, netherLandsPartition[0]);
        process1(arr, netherLandsPartition[1], right);
    }

    public static void main(String[] args) {
        int times = 100_0000;
        boolean s = true;
        for (int i = 0; i < times; i++) {
            int[] arr1 = ArrayCompareHelper.newRandomArray(50, 50, -50);
            int[] arr2 = ArrayCompareHelper.copyArray(arr1);
            int[] arr3 = ArrayCompareHelper.copyArray(arr1);
            int[] arr4 = ArrayCompareHelper.copyArray(arr1);
            quickSort1(arr1);
            quickSort2(arr2);
            quickSort3(arr3);
            ArrayCompareHelper.comparator(arr4);
            if (!ArrayCompareHelper.checkEquals(arr1, arr2)
                    || !ArrayCompareHelper.checkEquals(arr2, arr3)
                    || !ArrayCompareHelper.checkEquals(arr3, arr4)
            ) {
                s = false;
                ArrayCompareHelper.printArray(arr1);
                ArrayCompareHelper.printArray(arr2);
                ArrayCompareHelper.printArray(arr3);
                ArrayCompareHelper.printArray(arr4);
                break;
            }
        }
        System.out.println(s ? "OK" : "NO");
    }
}
